from typing import List

"""
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

 

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]
 

提示：

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

"""


# class Solution:
#     def sortColors(self, nums: List[int]) -> None:
#         """
#         荷兰国旗算法，使用双指针，原地排序
#         """
#         p0, curr, p2 = 0, 0, len(nums) - 1
#
#         while curr <= p2:
#             if nums[curr] == 0:
#                 nums[p0], nums[curr] = nums[curr], nums[p0]
#                 p0 += 1
#                 curr += 1
#             elif nums[curr] == 2:
#                 nums[p2], nums[curr] = nums[curr], nums[p2]
#                 p2 -= 1
#             else:
#                 curr += 1

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        left = 0
        cur = 0
        right = len(nums) - 1

        while cur <= right:
            if nums[cur] == 0:
                nums[left], nums[cur] = nums[cur], nums[left]
                cur += 1
                left += 1
            elif nums[cur] == 2:
                nums[right], nums[cur] = nums[cur], nums[right]
                right -= 1
            else:
                cur += 1


if __name__ == "__main__":
    s = Solution()
    nums = [2, 0, 1, 0, 1, 2, 0]
    s.sortColors(nums)
    print("排序后：", nums)
